#include "mtBasic.h"
#include <iostream>
int getDis(std::vector<int> &A, int n) {
    const int N = A.size();
    if (N == 0)
        return 0;
    int minValue = A[0];
    int maxDis = 0;
    for (auto e : A) {
        if (e < minValue)
            minValue = std::min(e, minValue);
        maxDis = std::max(maxDis, e - minValue);
    }
    return maxDis;
}
std::vector<std::vector<int>> flipChess(std::vector<std::vector<int>> &A,
                                        std::vector<std::vector<int>> &f) {
    int rows = A.size();
    int cols = A[0].size();
    for (auto loc : f) {
        int x = loc[0] - 1;
        int y = loc[1] - 1;
        int left_limit = y - 1;
        int right_limit = y + 1;
        int upper_limit = x - 1;
        int bottom_limit = x + 1;
        if (left_limit >= 0)
            A[x][left_limit] = A[x][left_limit] == 1 ? 0 : 1;
        if (right_limit < cols)
            A[x][right_limit] = A[x][right_limit] == 1 ? 0 : 1;
        if (upper_limit >= 0)
            A[upper_limit][y] = A[upper_limit][y] == 1 ? 0 : 1;
        if (bottom_limit < rows)
            A[bottom_limit][y] = A[bottom_limit][y] == 1 ? 0 : 1;
    }
    return A;
}
void dfsPath(std::vector<std::vector<int>> &CityMap, int x, int y, int n, int m,
             std::unordered_map<int, int> &cache, int path_nums,
             std::vector<std::vector<bool>> &visited) {
    // 越界
    if (x < 0 || x >= n || y < 0 || y >= m)
        return;
    // 位置已经访问过或者到达不可访问区域
    else if (visited[x][y] || CityMap[x][y] == -1 ||
             (cache.size() > 0 && path_nums > cache.begin()->first))
        return;
    else if (CityMap[x][y] == 2) {
        cache[path_nums] += 1;
    } else {
        visited[x][y] = true;

        dfsPath(CityMap, x - 1, y, n, m, cache, path_nums + 1, visited);
        dfsPath(CityMap, x + 1, y, n, m, cache, path_nums + 1, visited);
        dfsPath(CityMap, x, y - 1, n, m, cache, path_nums + 1, visited);
        dfsPath(CityMap, x, y + 1, n, m, cache, path_nums + 1, visited);
        visited[x][y] = false;
    }
}

int countPath(std::vector<std::vector<int>> &CityMap, int n, int m) {
    vector<vector<bool>> visited =
        vector<vector<bool>>(n, vector<bool>(m, false));
    unordered_map<int, int> cache;

    int path_nums = 0;
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < m; c++) {
            if (CityMap[r][c] == 1) {
                dfsPath(CityMap, r, c, n, m, cache, path_nums, visited);
                continue;
            }
        }
    }

    return cache.begin()->second;
}

int largestRectangleAreaBrute(vector<int> &heights) {
    const int n = heights.size();
    if (n == 0)
        return 0;
    else {
        int max_area = -1;

        for (int c_index = 0; c_index < n; c_index++) {
            int min_left = c_index, min_right = c_index;
            while (min_left - 1 >= 0 &&
                   heights[min_left - 1] >= heights[c_index])
                min_left--;
            while (min_right + 1 < n &&
                   heights[min_right + 1] >= heights[c_index])
                min_right++;
            max_area =
                max(max_area, (min_right - min_left + 1) * heights[c_index]);
        }
        return max_area;
    }
}

int largestRectangleArea(vector<int> &heights) {
    const int n = heights.size();
    stack<int> area_stack;
    int index;
    int max_value = 0;
    heights.push_back(0); // 保证只有一个元素的时候能运算
    for (int i = 0; i < heights.size(); i++) {
        while (!area_stack.empty() && heights[i] <= heights[area_stack.top()]) {
            auto temp = area_stack.top();
            area_stack.pop();
            if (area_stack.empty())
                max_value = max(max_value, i * heights[temp]);
            else
                max_value =
                    max(max_value, heights[temp] * (i - area_stack.top() - 1));
        }
        area_stack.push(i);
    }
    return max_value;
}

int maximalRectangle(std::vector<std::vector<char>> &matrix) {
    if (matrix.empty())
        return 0;
    int rows = matrix.size();
    int cols = matrix[0].size();

    std::vector<int> heights = std::vector<int>(cols + 1, 0);
    int max_value = 0;
    heights[cols] = -1;
    for (int row = 0; row < rows; row++) {
        for (int col = 0; col < cols; col++) {
            if (matrix[row][col] == '0')
                heights[col] = 0;
            else
                heights[col] += 1;
        }
        max_value = std::max(max_value, largestRectangleArea(heights));
    }
    return max_value;
}
